/* RMQ 区间最大值问题 Range - Minimum/Maximum Query
*   f[i][j]表示从i开始长度是2^j的区间中，最大值是多少
    f[i][j] = max(f[i][j-1],f[i+2^(j-1)][j-1]);
    缺点：包含点太多，不支持修改
* 本题:
    RMQ板子题
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream> 
#include <cmath>  
using namespace std;
#define int long long
const int N = 2e5+10, M = 18; //lg(2*10^5) ~ 18
int n, m;
//int w[N];
int f[N][M];

void init()
{
    for(int j = 1; j < M; j++)
        for(int i = 1; i + (1<< j) - 1 <= n; i++)
            //if(!j) f[i][j] = w[i];
            f[i][j] = max(f[i][j-1], f[i+(1<<j-1)][j-1]);
}

int query(int l, int r)
{
    int len = r-l+1;
    int k = log(len)/log(2); 
    return max(f[l][k], f[r-(1<<k) +1][k]);
}
signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> f[i][0]; //边界s[i][0] = a[i]
    //for(int i = 1; i <= n; i++) cin >> w[i]; 

    init();

    cin >> m;
    while(m--)
    {
        int l, r; cin >> l >> r;
        cout << query(l, r) << endl;
    }
    return 0;
}